import java.util.*;

/**
 * 单源最短路问题
 */
public class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};

    /**
     * 迷宫中离入口最近的出口
     * @param maze
     * @param entrance
     * @return
     */
    public int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length;
        int n = maze[0].length;
        boolean[][] vis = new boolean[m][n]; // 记录当前位置是否已走过
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < 4; i++) {
            int a = entrance[0] + dx[i];
            int b = entrance[1] + dy[i];
            if (a >= 0 && a < m && b >= 0 && b < n && !vis[a][b] && maze[a][b] == '.') {
                vis[a][b] = true;
                queue.add(new int[]{a, b});
            }
        }
        // queue.add(entrance);
        vis[entrance[0]][entrance[1]] = true;
        int count = 1;
        boolean flg = false;
        while(!queue.isEmpty()) {
            int k = queue.size();
            // 弹出所有元素
            while(k > 0) {
                int[] tmp = queue.poll();
                int x = tmp[0], y = tmp[1];
                // 判断当前位置是否已是出口
                if (x <= 0 || x >= m - 1 || y <= 0 || y >= n - 1) {
                    flg = true;
                    break;
                }
                // 放入下一层元素
                for(int i = 0; i < 4; i++) {
                    int a = x + dx[i];
                    int b = y + dy[i];
                    if (a >= 0 && a < m && b >= 0 && b < n && !vis[a][b] && maze[a][b] == '.') {
                        vis[a][b] = true;
                        queue.add(new int[]{a, b});
                    }
                }
                k--;
            }
            if (flg) {
                break;
            }
            count++;
        }
        return flg ? count: -1;
    }

    /**
     * 最小基因变化
     * @param startGene
     * @param endGene
     * @param bank
     * @return
     */
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> vis = new HashSet<>(); // 标记搜索过的状态
        Set<String> hash = new HashSet<>(); // bank 中的状态
        for(String str: bank) {
            hash.add(str);
        }
        // 处理特殊情况
        if (startGene.equals(endGene)) return 0;
        if (!hash.contains(endGene)) return -1;

        char[] change = {'A', 'C', 'G', 'T'};
        Queue<String> queue = new LinkedList<>();
        queue.add(startGene);
        int step = 0;
        while(!queue.isEmpty()) {
            step++;
            int sz = queue.size();
            while(sz-- > 0) {
                String str = queue.poll();
                for(int i = 0; i < 8; i++) {
                    char[] tmp = str.toCharArray();
                    for(int j = 0; j < 4; j++) {
                        tmp[i] = change[j];
                        String next = new String(tmp);
                        if (hash.contains(next) && !vis.contains(next)) {
                            if (next.equals(endGene)) return step;
                            queue.add(next);
                            vis.add(next);
                        }
                    }
                }
            }
        }
        return -1;
    }

    /**
     * 单词接龙
     * @param beginWord
     * @param endWord
     * @param wordList
     * @return
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> vis = new HashSet<>();
        Set<String> hash = new HashSet<>();
        for(String s: wordList) {
            hash.add(s);
        }
        if (!hash.contains(endWord)) return 0;
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        vis.add(beginWord);
        int step = 1;
        while (!queue.isEmpty()) {
            step++;
            int sz = queue.size();
            while (sz-- > 0) {
                String s = queue.poll();
                for (int i = 0; i < s.length(); i++) {
                    char[] tmp = s.toCharArray();
                    for (char j = 'a'; j <= 'z'; j++) {
                        tmp[i] = j;
                        String next = new String(tmp);
                        if (next.equals(endWord)) return step;
                        if (hash.contains(next) && !vis.contains(next)) {
                            queue.add(next);
                            vis.add(next);
                        }
                    }
                }
            }
        }
        return 0;
    }

    int m, n;

    /**
     * 为高尔夫比赛砍树
     * @param forest
     * @return
     */
    public int cutOffTree(List<List<Integer>> forest) {
        // 先找出砍树顺序
        Map<Integer, int[]> hash = new HashMap<>();
        m = forest.size();
        n = forest.get(0).size();
        List<Integer> order = new ArrayList<>();
        for(int i = 0; i < m; i++) {
            List<Integer> tmp = forest.get(i);
            for(int j = 0; j < n; j++) {
                if (tmp.get(j) > 1) {
                    order.add(tmp.get(j));
                    hash.put(tmp.get(j), new int[]{i, j});
                }
            }
        }
        // 进行排序
        Collections.sort(order);
        int bx = 0, by = 0; // 起点
        int res = 0;
        // 转化为迷宫问题
        for(int i = 0; i < order.size(); i++) {
            int[] tmp = hash.get(order.get(i));
            int a = tmp[0];
            int b = tmp[1];
            int step = bfs(forest, bx, by, a, b);
            if (step == -1) return -1;
            res += step;
            bx = a;
            by = b;
        }
        return res;
    }

    private int bfs(List<List<Integer>> forest, int bx, int by, int ex, int ey) {
        if (bx == ex && by == ey) return 0;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] vis = new boolean[m][n];
        queue.add(new int[]{bx, by});
        vis[bx][by] = true;
        int step = 0;
        while (!queue.isEmpty()) {
            step++;
            int sz = queue.size();
            while (sz-- > 0) {
                int[] tmp = queue.poll();
                int a = tmp[0];
                int b = tmp[1];
                for (int i = 0; i < 4; i++) {
                    int x = a + dx[i];
                    int y = b + dy[i];
                    if (x >= 0 && x < m
                            && y >= 0 && y < n
                            && forest.get(x).get(y) != 0
                            && !vis[x][y]) {
                        if (x == ex && y == ey) {
                            return step;
                        }
                        queue.add(new int[]{x, y});
                        vis[x][y] = true;
                    }
                }
            }
        }
        return -1;
    }

//    public int cutOffTree(List<List<Integer>> f) {
//        m = f.size(); n = f.get(0).size();
//        List<int[]> trees = new ArrayList<>();
//        for(int i = 0; i < m; i++) {
//            for(int j = 0; j < n; j++) {
//                if(f.get(i).get(j) > 1)
//                    trees.add(new int[]{i, j});
//            }
//        }
//        Collections.sort(trees, (a, b) -> {
//            return f.get(a[0]).get(a[1]) - f.get(b[0]).get(b[1]);
//        });
//        int bx = 0, by = 0;
//        int ret = 0;
//        for(int[] next : trees) {
//            int a = next[0], b = next[1];
//            int step = bfs(f, bx, by, a, b);
//            if(step == -1) return -1;
//            ret += step;
//            bx = a; by = b;
//        }
//        return ret;
//    }
//    public int bfs(List<List<Integer>> f, int bx, int by, int ex, int ey) {
//        if(bx == ex && by == ey) return 0;
//        Queue<int[]> q = new LinkedList<>();
//        boolean[][] vis = new boolean[m][n];
//        q.add(new int[]{bx, by});
//        vis[bx][by] = true;
//        int step = 0;
//        while(!q.isEmpty()) {
//            int sz = q.size();
//            step++;
//            while(sz-- != 0) {
//                int[] t = q.poll();
//                int a = t[0], b = t[1];
//                for(int i = 0; i < 4; i++) {
//                    int x = a + dx[i], y = b + dy[i];
//                    if(x >= 0 && x < m && y >= 0 && y < n && f.get(x).get(y) != 0 && !vis[x][y]) {
//                        if(x == ex && y == ey) return step;
//                        q.add(new int[]{x, y});
//                        vis[x][y] = true;
//                    }
//                }
//            }
//        }
//        return -1;
//    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        char[][] maze = {{'+', '+', '+'}, {'.', '.', '.'}, {'+', '+', '+'}};
//        solution.nearestExit(maze, new int[]{1, 0});
//        solution.ladderLength("hit", "cog", Arrays.asList("hot","dot","dog","lot","log","cog"));
        List<List<Integer>> lists = new ArrayList<>(Arrays.asList(
                new ArrayList<>(Arrays.asList(2, 3, 4)),
                new ArrayList<>(Arrays.asList(0, 0, 5)),
                new ArrayList<>(Arrays.asList(8, 7, 6))
        ));
        solution.cutOffTree(lists);
    }
}
